package basic.LRU;

/**
 * Created by zhouliang on 2017-04-04.
 */
public class LRUPageFrame {
    private static class Node {
        Node prev;
        Node next;
        int pageNum;
        Node() {
        }
    }

    private int capacity;

    private int currentSize;
    private Node first;// 链表头
    private Node last;// 链表尾


    public LRUPageFrame(int capacity) {
        this.currentSize = 0;
        this.capacity = capacity;
    }

    /**
     * 获取缓存中对象
     * @param pageNum
     * @return
     */
    public void access(int pageNum) {
        Node node = find(pageNum);
        //在该队列中存在， 则提到队列头
        if (node != null) {
            moveExistingNodeToHead(node);
        } else{
            node = new Node();
            node.pageNum = pageNum;
            // 缓存容器是否已经超过大小.
            if (currentSize >= capacity) {
                removeLast();
            }
            addNewNodetoHead(node);
        }
    }

    private void addNewNodetoHead(Node node) {
        if(isEmpty()){
            node.prev = null;
            node.next = null;
            first = node;
            last = node;

        } else{
            node.prev = null;
            node.next = first;
            first.prev = node;
            first = node;
        }
        this.currentSize ++;
    }

    private Node find(int data){
        Node node = first;
        while(node != null){
            if(node.pageNum == data){
                return node;
            }
            node = node.next;
        }
        return null;

    }

    /**
     * 删除链表尾部节点 表示 删除最少使用的缓存对象
     */
    private void removeLast() {
        Node prev = last.prev;
        prev.next = null;
        last.prev = null;
        last = prev;
        this.currentSize --;
    }

    /**
     * 移动到链表头，表示这个节点是最新使用过的
     *
     * @param node
     */
    private void moveExistingNodeToHead(Node node) {
        if (node == first) {
            return;
        }
        else if(node == last){
            //当前节点是链表尾， 需要放到链表头
            Node prevNode = node.prev;
            prevNode.next = null;
            last.prev = null;
            last  = prevNode;
        } else{
            //node 在链表的中间， 把node 的前后节点连接起来
            Node prevNode = node.prev;
            prevNode.next = node.next;
            Node nextNode = node.next;
            nextNode.prev = prevNode;
        }
        node.prev = null;
        node.next = first;
        first.prev = node;
        first = node;
    }
    private boolean isEmpty(){
        return (first == null) && (last == null);
    }

    public String toString(){
        StringBuilder buffer = new StringBuilder();
        Node node = first;
        while(node != null){
            buffer.append(node.pageNum);
            node = node.next;
            if(node != null){
                buffer.append(",");
            }
        }
        return buffer.toString();
    }
}
